home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ASME's Mechanical Engine…ing Toolkit 1997 December
/
ASME's Mechanical Engineering Toolkit 1997 December.iso
/
ai
/
prlg195b.lzh
/
GRAMMAR.LZH
/
ATN.PRO
Wrap
Text File
|
1987-12-08
|
10KB
|
385 lines
/* -------------------------------------------------------------------------
ATN.PRO by Eugene L. Frassetto
-------------------------------------------------------------------------
This is a simple, basic Augmented Transition Net for parsing an
English sentence.
The typed sentence is converted to a list of words and a parse tree is
returned. The parse tree will always have the infinitive form of the
verb. e.g.
The boy hit the ball.
becomes [the,boy,hit,the,ball,.]
=> [[the,boy],[hit,[the,ball]],[.]]
The boy with the bat hit the big green ball.
becomes [the,boy,with,the,bat,hit,the,big,green,ball,.]
=> [[[the,boy],[with,[the,bat]]],[hit,[the,big,green,ball]],[.]]
Is John going?
becomes [is,john,going,with,us?]
=> [[john],[[is],[to,go],[with,us]]]],[?]]
Can John drive the red car with the big dog?
becomes [can,john,drive,the,red,car,with the big,dog,?]
=> [[john],[[can],[drive,[[the,red,car],[with,[the,big,dog]]]]],[?]]
What are cars?
becomes [what,are,cars,?]
=> [[cars],[are,[what]],[?]]
Note from Bob Morein:
Further examples:
Where is the boy? ( wh_word, aux_verb )
Where go the boy? ( wh_word, verb )
The grammar for this ATN is:
S --> NP VP '.' (declarative)
S --> VP '!' (imperative - you understood)
S --> AUX_VERB NP ING_VP '?' (yes-no question)
S --> MODAL NP VP '?' (yes-no question)
S --> WH_WORD AUX_VERB NP '?' (wh question)
S --> WH_WORD VERB '?' (wh question)
NP --> PROPER_NOUN
NP --> PRONOUN
NP --> DETERMINER NOUN
NP --> DETERMINER ADJs NOUN
NP --> NP PP
ADJs --> ADJECTIVE ADJs
PP --> PREPOSITION NP
VP --> VERB
VP --> VERB NP
VP --> VERB PP
Using the second example above, the parse tree is:
S
|
+-------------------------+---+----------------------+
| | |
NP VP |
+------+------+ | |
| | | |
| PP | |
| | | |
| +----+---+ +-----+-----+ |
| | | | | |
NP | NP | NP |
| | | | | |
+-+-+ | +-+-+ | +---+-+--+----+ |
| | | | | | | | | | |
DET NOUN PREP DET NOUN VERB DET ADJ ADJ NOUN FINAL_PUNC
| | | | | | | | | | |
[ [ [the,boy], [with, [the,bat] ] ], [hit, [the,big,green,ball] ], [.] ]
To start things off type 'go.'
You will be prompted to enter a sentence.
Note from Bob Morein: You must not backspace while entering the
sentence. If you make a mistake, type a period, hit return, and
the program will process your error and then return for more
input.
To exit the parser type "quit." (without the quotes) when prompted
to enter a sentence.
------------------------------------------------------------------------- */
go :-
repeat,
print( ' Enter a sentence.' ), nl,
read_in( P ), nl,
( (P = [quit,.], ! );
( ( parse( P, Tree ),
print( Tree ), nl,
fail );
( not( parse( P, _ ) ),
print( 'Not a valid sentence.' ), nl,
fail ) ) ).
/* parse a simple declarative sentence */
parse( P, Ptree ) :-
( npp( P, Np, Rest );
np( P, Np, Rest ) ), !,
vp( Rest, Vp, [Fp] ), !,
Fp = '.', !,
Ptree = [Np, Vp, [Fp]].
/* parse an imperative sentence (insert 'you') */
parse( P, Ptree ) :-
vp( P, Vp, [Fp] ), !,
( Fp = '!';
Fp = '.'), !,
Ptree = [[you], Vp, [Fp]].
/* parse a yes-no question which starts with is, are, etc. */
parse( [Aux | P], Ptree ) :-
aux_verb( Aux ), !,
np( P, Np, [First | Rest] ), !,
ing_base( First, Base ), !,
vp( [Base | Rest], Vp, [Fp] ), !,
Fp = '?', !,
Ptree = [Np, [[Aux], [to | Vp]], [Fp]].
/* parse a yes-no question which starts with can, will, etc. */
parse( [Modal | P], Ptree ) :-
modal( Modal ), !,
np( P, Np, Rest ), !,
vp( Rest, Vp, [Fp] ), !,
Fp = '?', !,
Ptree = [Np, [[Modal], Vp], [Fp]].
/* ---------------------------------------------------------------------- */
/* parse a 'wh-word verb' question */
parse( [Wh, Verb | Rest], Ptree ) :-
wh_word( Wh ),
verb( Verb ), !,
( npp( Rest, Np, [Fp] );
np( Rest, Np, [Fp] ) ), !,
Fp = '?', !,
Ptree = [[Wh], [Verb, Np], [Fp]].
/* parse a 'wh-word aux_verb' question */
parse( [Wh, Aux | Rest], Ptree ) :-
wh_word( Wh ),
aux_verb( Aux ), !,
( npp( Rest, Np, [Fp] );
no( Rest, Np, [Fp] );
np( Rest, Np, [Fp] ) ), !,
Fp = '?', !,
Ptree = [Np, [Aux, [Wh]], [Fp]].
/* ------------------------------------------------------------------------ */
/* noun phrase containing pronoun or a proper noun */
np( [Pnoun | T], [Pnoun], T ) :-
( pnoun( Pnoun );
pronoun( Pnoun ) ),
!.
/* noun phrase with an attached prepositional phrase */
npp( S, [Np, Pp], Rest ) :-
np( S, Np, Rest1 ),
pp( Rest1, Pp, Rest ),
!.
/* noun phrase with a determiner and a noun */
np( [Det, Noun | T], [Det, Noun], T ) :-
s_noun( Noun, Snoun ),
det( Det ),
!.
/* noun phrase with a determiner, adjective and noun */
np( [Det, Adj, Noun | T], [Det, Adj, Noun], T ) :-
det( Det ),
adj( Adj ),
s_noun( Noun, Snoun ),
!.
/* noun phrase with a det adjs and a noun */
np( [Det, Adj | T], Np, Rest ) :-
det( Det ),
adj( Adj ),
adjs( T, Adjs, [Noun | Rest] ),
s_noun( Noun, Snoun ),
append( Adjs, [Noun], X ),
append( [Det, Adj], X, Np ),
!.
/* noun alone for special cases */
no( [Noun | Rest], [Noun], Rest ) :-
s_noun( Noun, _ ),
!.
no( [Adj, Noun | Rest], [Adj, Noun], Rest) :-
adj( Adj ), !,
s_noun( Noun, _ ),
!.
adjs( [Adj | T], Adjs, T ) :-
not( adj( Adj ) ).
adjs( [Adj | T], Adjs, T ) :-
adj( Adj ),
adjs( T, X, Rest ),
append( [Adj], X, Adjs ).
/* prepositional phrase */
pp( [Prep | T], [Prep, Np], Rest ) :-
prep( Prep ),
np( T, Np, Rest ),
!.
/* verb phrase containing a verb and a noun phrase */
vp( [Verb | T], [Verb, Np], Rest ) :-
verb( Verb ),
( npp( T, Np, Rest );
np( T, Np, Rest ) ),
!.
/* verb phrase with just a verb */
vp( [Verb | Rest], [Verb], Rest ) :-
verb( Verb ),
!.
/* verb phrase with a verb and either a np, a np and pp or a pp by itself
this is for the yes-no questions */
vp( [Verb | T], [Verb, Np], Rest ) :-
verb( Verb ),
( npp( T, Np, Rest );
np( T, Np, Rest );
pp( T, Np, Rest ) ),
!.
/* --------------------------------------------- */
/* */
/* word morphology predicates */
/* */
/* --------------------------------------------- */
/* get base of an ing verb */
/* verb with double consonant - hitting => hit */
ing_base( Test, Base ) :-
name( Test, X ),
reverse( X, [_,_,_,_ | Y]),
reverse( Y, Z ),
name( Base, Z ),
verb( Base ).
/* regular verb - going => go */
ing_base( Test, Base ) :-
name( Test, X ),
reverse( X, [_,_,_ | Y]),
reverse( Y, Z ),
name( Base, Z ),
verb( Base ).
/* verb ending with 'e' - driving => drive */
ing_base( Test, Base ) :-
name( Test, X ),
reverse( X, [_,_,_ | Y]),
reverse( [101 | Y], Z ),
name( Base, Z ),
verb( Base ).
/* get the singular of a plural noun */
/* cars => car, car => car, walk => FALSE */
s_noun( P, S ) :-
noun( P ), !,
S = P.
s_noun( P, S ) :-
name( P, X ),
reverse( X, [_ | Y] ),
reverse( Y, Z ),
name( S, Z ), !,
noun( S ),
!.
/* the dictionary */
pnoun( john ).
pnoun( mary ).
pronoun( he ).
pronoun( him ).
pronoun( she ).
pronoun( her ).
pronoun( i ).
pronoun( me ).
pronoun( we ).
pronoun( us ).
pronoun( you ).
noun( boy ).
noun( ball ).
noun( bat ).
noun( dog ).
noun( car ).
wh_word( who ).
wh_word( what ).
wh_word( when ).
wh_word( where ).
det( a ).
det( an ).
det( the ).
adj( big ).
adj( small ).
adj( green ).
adj( red ).
adj( long ).
adj( short ).
prep( with ).
prep( in ).
prep( to ).
verb( hit ).
verb( go ).
verb( run ).
verb( swim ).
verb( drive ).
verb( walk ).
aux_verb( is ).
aux_verb( are ).
modal( will ).
modal( can ).
final_punc( '.' ).
final_punc( '?' ).
final_punc( '!' ).
/* ------------------------------------------------------ *
* *
* misc. aux and helper predicates *
* *
* ----------------------------------------------------- */
/* append two lists - [a,b,c],[d,e,f] => [a,b,c,d,e,f] */
append( [], AnyList, AnyList).
append( [Head | Tail], List2, [Head | NewTail] ) :-
append( Tail, List2, NewTail ).
/* reverse a list - [a,b,c] => [c,b,a] */
reverse([F], [F]).
reverse([H | T], X) :-
reverse(T, Y),
append(Y, [H], X).
/* ---------------------------------------------------------------- *
* *
* The following code is from the file RSENT.PRO. *
* It inputs a sentence and returns it as a list. *
* (it dosen't handle backspace so type with care) *
* *
* my thanks to its' author. *
* *
* ---------------------------------------------------------------- */
read_in([W|Ws]) :- get0(C), readword(C,W,C1), restsent(W,C1,Ws).
restsent( W,_,[]) :- final_punc(W), !.
restsent(W,C,[W1|Ws]) :- readword(C,W1,C1), restsent(W1,C1,Ws).
readword(C,W,C1) :- single_character(C), !, name(W,[C]), get0(C1).
readword(C,W,C2) :-
in_word(C,NewC), !,
get0(C1),
restword(C1,Cs,C2),
name(W,[NewC|Cs]).
readword(C,W,C2) :- get0(C1), readword(C1,W,C2).
restword(C,[NewC|Cs],C2) :-
in_word(C,NewC), !,
get0(C1),
restword(C1,Cs,C2).
restword(C,[],C).
single_character(63). /* ? */
single_character(33). /* ! */
single_character(46). /* . */
in_word(C,C) :- C>96, C<123. /* a b..z */
in_word(C,L) :- C>64, C<91, L is C+32. /* A,B..Z */